package _binary_tree

import common.TreeNode
import org.junit.Assert
import org.junit.Test

/**
 * https://leetcode.cn/problems/range-sum-of-bst/description
```
938. 二叉搜索树的范围和
给定二叉搜索树的根结点 root，返回值位于范围 [low, high] 之间的所有结点的值的和。

示例 1：
输入：root = [10,5,15,3,7,null,18], low = 7, high = 15
输出：32

示例 2：
输入：root = [10,5,15,3,7,13,18,1,null,6], low = 6, high = 10
输出：23

提示：
树中节点数目在范围 [1, 2 * 104] 内
1 <= Node.val <= 105
1 <= low <= high <= 105
所有 Node.val 互不相同

```
 */
class leetcode_938 {
    @Test
    fun test_1() {
        val n3 = TreeNode(3)
        val n7 = TreeNode(7)
        val n5 = TreeNode(5)
        val n10 = TreeNode(10)
        val n15 = TreeNode(15)
        val n18 = TreeNode(18)

        val root = n10
        n10.left = n5
        n10.right = n15

        n5.left = n3
        n5.right = n7

        n15.right = n18
        val actual = rangeSumBST(root, 7, 15)
        val expected = 32
        Assert.assertEquals(expected, actual)
    }

    private fun rangeSumBST(root: TreeNode?, low: Int, high: Int): Int {
        /**
        题型：二叉树的中序遍历
        思路：
        根据二叉搜索树的大小关系：左 < 中 < 右：
        当左节点 >= low 时，计算左节点的sum
        当节点 在 [low, high] 时，计算当前当前节点
        当右节点 >= high 时，计算右节点的sum
        然后返回 左节点sum + 当前节点 + 右节点sum
         */

        // 1 确定函数返回值以及参数
        // 2 确定终止条件
        if (root == null) {
            return 0
        }
        // 3 确定单层递归的处理逻辑

        // 左
        var leftSum: Int = 0
//        if (root.`val` >= low) { // 这个条件可以省略，加上可以去掉不必要的递归
        if (root.`val` > low) { // 这个条件可以省略，加上可以去掉不必要的递归
            leftSum = rangeSumBST(root.left, low, high)
        }

        // 中
        var n: Int = 0
        if (root.`val` in low..high) {
            n = root.`val`
        }

        // 右
        var rightSum: Int = 0
//        if (root.`val` <= high) { // 这个条件可以省略，加上可以去掉不必要的递归
        if (root.`val` < high) { // 这个条件可以省略，加上可以去掉不必要的递归
            rightSum = rangeSumBST(root.right, low, high)
        }
        return leftSum + n + rightSum
    }
}